package com.shm.leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 491. 递增子序列
 * 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
 *
 * 示例:
 *
 * 输入: [4, 6, 7, 7]
 * 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
 * 说明:
 *
 * 给定数组的长度不会超过15。
 * 数组中的整数范围是 [-100,100]。
 * 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
 * @author SHM
 */
public class FindSubsequences {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();

    /**
     * 方法二：递归枚举 + 减枝
     * 思路与算法
     * 这是一个递归枚举子序列的通用模板，即用一个临时数组 \rm temptemp 来保存当前选出的子序列，使用 \rm curcur 来表示当前位置的下标，在 dfs(cur, nums) 开始之前，[0, {\rm cur} - 1][0,cur−1] 这个区间内的所有元素都已经被考虑过，而 [{\rm cur}, n][cur,n] 这个区间内的元素还未被考虑。在执行 dfs(cur, nums) 时，我们考虑 {\rm cur}cur 这个位置选或者不选，如果选择当前元素，那么把当前元素加入到 \rm temptemp 中，然后递归下一个位置，在递归结束后，应当把 \rm temptemp 的最后一个元素删除进行回溯；如果不选当前的元素，直接递归下一个位置。
     *
     * 当然，如果我们简单地这样枚举，对于每一个子序列，我们还需要做一次 O(n)O(n) 的合法性检查和哈希判重复，在执行整个程序的过程中，我们还需要使用一个空间代价 O(2^n)O(2
     * n
     *  ) 的哈希表来维护已经出现的子序列的哈希值。我们可以对选择和不选择做一些简单的限定，就可以让枚举出来的都是合法的并且不重复：
     *
     * 使序列合法的办法非常简单，即给「选择」做一个限定条件，只有当前的元素大于等于上一个选择的元素的时候才能选择这个元素，这样枚举出来的所有元素都是合法的
     *
     * 那如何保证没有重复呢？我们需要给「不选择」做一个限定条件，只有当当前的元素不等于上一个选择的元素的时候，才考虑不选择当前元素，直接递归后面的元素。因为如果有两个相同的元素，我们会考虑这样四种情况：
     *
     * 前者被选择，后者被选择
     * 前者被选择，后者不被选择
     * 前者不被选择，后者被选择
     * 前者不被选择，后者不被选择
     * 其中第二种情况和第三种情况其实是等价的，我们这样限制之后，舍弃了第二种，保留了第三种，于是达到了去重的目的。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(2^n \cdot n)O(2
     * n
     *  ⋅n)。仍然需要对子序列做二进制枚举，枚举出的序列虽然省去了判断合法性和哈希的过程，但是仍然需要 O(n)O(n) 的时间添加到答案中。
     * 空间复杂度：O(n)O(n)。这里临时数组的空间代价是 O(n)O(n)，递归使用的栈空间的空间代价也是 O(n)O(n)。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/increasing-subsequences/solution/di-zeng-zi-xu-lie-by-leetcode-solution/
     * @param nums
     * @return
     */
    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(0,Integer.MIN_VALUE,nums);
        return res;
    }

    public void dfs(int cur,int last,int[] nums){
        if(cur == nums.length){
            if(list.size()>=2){
                res.add(new ArrayList<Integer>(list));
            }
            return;
        }
        if(nums[cur]>=last){
            list.add(nums[cur]);
            dfs(cur+1,nums[cur],nums);
            list.remove(list.size()-1);
        }
        if(nums[cur]!=last){
            dfs(cur+1,last,nums);
        }
    }



    // 定义全局变量保存结果
//    List<List<Integer>> res = new ArrayList<>();

    /**
     * 题目分析
     * 定义全局变量 List<List<Integer>> res 保存结果；
     * 定义 dfs(int[] nums, int idx, List<Integer> curList) 进行搜索；
     * 参数 int idx 表示当前搜索到的数组下标，初始化为 -1，每次在 [idx + 1, nums.length - 1] 范围内遍历搜索递增序列的下一个值。
     * 参数 List<Integer> curList 表示当前的递增序列，只要长度大于 1，就拷贝一份存入结果列表 res 中。
     * 每次在 [idx + 1, nums.length - 1] 范围内遍历搜索递增序列的下一个值时，借助 set 进行去重，如果当前的值已经在 set 中了，则终止此路径继续搜索。
     *
     * 作者：sweetiee
     * 链接：https://leetcode-cn.com/problems/increasing-subsequences/solution/jin-tian-wo-you-shuang-ruo-zhuo-neng-miao-dong-la-/
     * @param nums
     * @return
     */
    public List<List<Integer>> findSubsequences_1(int[] nums) {
        // idx 初始化为 -1，开始 dfs 搜索。
        dfs(nums, -1, new ArrayList<>());
        return res;
    }

    private void dfs(int[] nums, int idx, List<Integer> curList) {
        // 只要当前的递增序列长度大于 1，就加入到结果 res 中，然后继续搜索递增序列的下一个值。
        if (curList.size() > 1) {
            res.add(new ArrayList<>(curList));
        }

        // 在 [idx + 1, nums.length - 1] 范围内遍历搜索递增序列的下一个值。
        // 借助 set 对 [idx + 1, nums.length - 1] 范围内的数去重。
        Set<Integer> set = new HashSet<>();
        for (int i = idx + 1; i < nums.length; i++) {
            //值相同的情况，后一个为序列的开始结果已包含了
            // 1. 如果 set 中已经有与 nums[i] 相同的值了，说明加上 nums[i] 后的所有可能的递增序列之前已经被搜过一遍了，因此停止继续搜索。
            if (set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            // 2. 如果 nums[i] >= nums[idx] 的话，说明出现了新的递增序列，因此继续 dfs 搜索（因为 curList 在这里是复用的，因此别忘了 remove 哦）
            if (idx == -1 || nums[i] >= nums[idx]) {
                curList.add(nums[i]);
                dfs(nums, i, curList);
                curList.remove(curList.size() - 1);
            }
        }
    }
}
